package com.markus.code.top100;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/30 16:20
 * todo: 分割等和子集
 */
public class LeetCode_416 {
    /**
     * 暴力解决 肯定通不过测试
     * @param nums
     * @return
     */
    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length == 0){
            return false;
        }
        int sum = getSum(nums);
        if (sum % 2 != 0){
            return false;
        }
        return process(nums,0,0,sum/2);
    }
    private boolean process(int []nums,int index,int sum,int target){
        if (index == nums.length){
            return sum==target;
        }
        return process(nums,index+1,sum+nums[index],target) ||
                process(nums,index+1,sum,target);
    }

    private int getSum(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum;
    }
    public boolean canPartitionWithDP(int[] nums) {
        if (nums == null || nums.length == 0){
            return false;
        }
        int sum = getSum(nums);
        if (sum % 2 != 0){
            return false;
        }
        boolean [][]dp = new boolean[nums.length][sum];
        //填基本数据
        dp[0][nums[0]] = true;
        //填普通数据
        for (int i=1;i<dp.length;i++){
            for (int j=1;j<dp[i].length;j++){
                dp[i][j] = dp[i-1][j];
                if (j-nums[i] >= 0){
                    dp[i][j] = dp[i-1][j-nums[i]] || dp[i][j];
                }
            }
        }
        return dp[nums.length-1][sum/2];
    }

    public static void main(String[] args) {
        int []num = {1,2,5};
        LeetCode_416 demo = new LeetCode_416();
        System.out.println(demo.canPartition(num));
        System.out.println(demo.canPartitionWithDP(num));
    }
}
